Section: New Results

Applications

Introduction

Nous présentons maintenant plusieurs travaux de nature appliquée, touchant à des domaines variés, dans lesquels nous exploitons certaines des techniques mathématiques présentées précédemment, et particulièrement celles qui relèvent de la théorie de Perron-Frobenius non-linéaire et de la convexité tropicale. Ces applications utilisent aussi des techniques d'algèbre linéaire ou d'optimisation convexe.

English version

In this section, we describe several applied works in which we use some of the theoretical tools developed by the team, including non-linear Perron-Frobenius theory and tropical convexity. Some of these applications also make an intensive use of linear algebraic and convex programming methods.

Propriétés des valeurs propres de Perron et de Floquet, et application en chronothérapeutique/Properties of Perron and Floquet eigenvalue, with an application to chronotherapeutics

Participants : Frédérique Billy [Projet BANG, INRIA] , Jean Clairambault [Projet BANG, INRIA] , Olivier Fercoq, Stéphane Gaubert, Thomas Lepoutre [Projet BANG puis DRACULA, INRIA] .

On s'intéresse à des modèles de systèmes dynamiques monotones structurés en âge représentant la croissance de populations de cellules (saines ou tumorales), à la suite de travaux de Clairambault et Perthame. Il s'agit de comprendre l'influence du contrôle circardien sur la croissance des cellules. Dans le cas stationnaire, le taux de croissance est représenté par une valeur propre de Perron. Dans le cas périodique, il s'agit d'une valeur propre de Floquet. Les travaux [42] , [52] , [58] portent sur l'identification de ces modèles ainsi que sur un problème de contrôle thérapeutique, consistant à minimiser le taux de croissance des cellules tumorales sous une contrainte de non-toxicité du traitement (maintien d'une population de cellules saines). Ce travail s'appuie en particulier sur un algorithme d'optimisation de la valeur propre de Perron d'une matrice développé par Fercoq dans un autre contexte [62] .

English version

We study monotone dynamical systems representing the growth of cells (healthy or tumoral), following a work of Clairambault and Perthame. The goal is to understand how the circadian control influences the growth of cells. In the case of stationnary monotone systems, this growth is measured by the Perron root. In the time periodic case, this Perron root is replaced by a Floquet multiplier.

The works [42] , [52] , [58] deal with the identification of these models, together with a therapeutic control problem, consisting in minimizing the growth rate of tumoral cells, under a non-toxicity constraint (preserving the population of healthy cells). This works relies in particular on a fast algorithm to optimize the Perron eigenvalue of a matrix, developed by Fercoq in a different context [62] .

Équations aux dérivées partielles en dynamique des populations/Partial differential equations from population dynamics

Participant : Sepideh Mirrahimi.

Un des problèmes sur lequel on a travaillé est un modèle de propagation de populations sexuées dans l'espace [64] où on dérive un modèle étudié par des biologistes, à partir d'un modèle de populations structurées et on étudie la dynamique de ce dernier. Nous avons aussi travaillé sur un problème de protéines moteurs, où nous étudions le comportement asymptotique d'un système de deux équations couplés de Fokker-Planck dans un environnement périodique. Avec une approche d'homogénéisation et en utilisant des techniques de solutions de viscosité, on montre que les protéines se déplacent dans une direction constante [65] . De plus, en utilisant des idées venant des problèmes similaires mais discrets, avec Stéphane Gaubert nous étudions les EDPs qui décrivent la dynamique d'une population asexuée sous l'effet des mutations et de la sélection naturelle, et on cherche à déterminer la limite en temps long de la densité de population.

English version

One of the problems studied is a model of propagation of a sexual population in space [64] , where we derive a model studied by biologists, from a structured population model. We then study the behavior of the solution to the latter model. We also have worked on a problem of motor proteins, where we study the asymptotic behavior of a time dependent, weakly coupled, Fokker-Planck system of two equations set in a periodic environment. By a homogenization approach and using viscosity solutions technics we prove that the molecules either move along a fixed filament with a constant speed and direction or remain immobile [65] . Moreover, using ideas coming from discrete models, with Stéphane Gaubert we study some PDEs that describe the dynamics of an asexual population under mutations and natural selection. We try to determine the long-time limit of the population density.

Identification du trafic dans les réseaux IP/Traffic identification in IP networks

Participants : Mustapha Bouhtou [Orange Labs] , Stéphane Gaubert, Guillaume Sagnol.

Le travail de thèse de Guillaume Sagnol, réalisé en collaboration avec Orange Labs dans le cadre d'un contrat “CRE”, a porté sur l'identification du trafic dans des réseaux IP, problème auquel il a appliqué des d'optimisation SDP et d'optimisation sous-modulaire afin de développer des algorithmes passant à l'échelle. Cette thèse s'est achevée fin 2010  [173] . Les articles suivants relatifs au travail de thèse ont été publiés cette année: [36] , [35] .

English version

The PhD work of Guillaume Sagnol, done in collaboration with Orange Labs in the framework of a “CRE” research contract, dealt with the identication of the trafic in IP networks. Sagnol applied SDP and submodular optimization techniques to develop saclable algorithms (adapted to large networks). The PhD defense took place in 2010  [173] . Some contributions of the Phd have been published this year in [36] , [35] .

Analyse statique de programmes et itération sur les politiques/Static analysis of computer programs and policy iteration

Participants : Assale Adjé, Stéphane Gaubert, Eric Goubault [CEA] .

La thèse d'A. Adjé [11] , encadrée conjointement par S. Gaubert et E. Goubault, traite de l'application de méthodes de théorie des jeux et d'optimisation (analyse convexe abstraite, programmation convexe et non convexe) aux problèmes de point fixe intervenant en analyse statique de programme. On a introduit dans [14] un nouveau domaine en analyse statique, qui étend au cas non-linéaire le domaine des “gabarits” introduit par Manna, Sankaranarayanan, and Sipma  [175] . Ce domaine permet de représenter des ensembles accessibles non-convexes (définis par un nombre fini d'inégalités prises dans un dictionnaire). Ceci permet d'intégrer en particulier des informations liées à l'existence de fonctions de Lyapunov, qui sont souvent connues dans les applications issues de l'ingénierie. Nous avons montré dans [14] que des invariants (expérimentalement précis) pouvaient être obtenus en couplant l'itération sur les politiques avec des relaxations de Shor (relaxations SDP de problèmes quadratiques non-convexes), ce qui fournit des abstractions précises de certains programmes numériques (ex: filtres avec seuils).

Un problème important consiste à déterminer le plus petit point fixe (l'algorithme de [14] fournit un point fixe, qui peut ne pas être minimal). Ce problème est abordé dans [30] , où l'approche de [14] est comparée avec une approche duale développée par Gawlitza et Seidl.

English version

The PhD work of A. Adjé [11] , co-supervised by S. Gaubert and E. Goubault, applies methods from game theory and optimization (generalized duality, convex and non convex programming) to the fixed point problems arising in static analysis of programs by abstract interpretation. We introduced in [14] a new domain in static analysis, which extends to nonlinear cases the “templates” introduced by Manna, Sankaranarayanan, and Sipma  [175] . This domain allows one to represent accessible sets that are non convex. These are defined by finitely many inequalities taken from a dictionnary. This allows one to use in particular the information provided by Lyapunov functions, which are often known in applications arising from engineering. We showed in [14] that experimentally accurate invariants can be obtained by coupling policy iteration with Shor relaxation (SDP relaxation of convex programming problems). This yields accurate abstractions of some numerical programs, like linear filters with thresholds.

An important problem consists in determining the smallest fixed point (the algorithm of [14] yields a possibly non minimal fixed point). This problem is addressed in [30] , in which the approach of [14] is compared with a dual approach developed by Gawlitza and Seidl.

Optimisation du référencement sur la toile/Optimization of web referencing

Participants : Marianne Akian, Mustapha Bouhtou [Orange Labs] , Olivier Fercoq, Stéphane Gaubert.

La thèse d'O. Fercoq, co-encadrée par M. Akian, M. Bouhtou, et S. Gaubert, financée par un CRE d'Orange Labs, a pour but d'appliquer des méthodes d'optimisation et de théorie des jeux à l'optimisation de services en lignes. On a tout d'abord étudié le problème de l'optimisation du référencement, que l'on formalise en se donnant par exemple un ensemble d'hyperliens et de ressources obligatoires, dont la nature et la position sur le site web sont déterminées à l'avance par le concepteur. Cet ensemble forme en quelque sorte le squelette du site web. On se donne aussi un ensemble d'hyperliens ou de ressources facultatives, pour lesquels le concepteur du site a certains degrés de liberté (le lien ou le contenu peut être mis sur une page plutôt qu'une autre, voire être omis).

Dans [61] , on aborde le problème de l'optimisation du “Pagerank” dans ce cadre, en appliquant des techniques de décision Markovienne classiques et sous-contraintes. Le problème peut en effet se ramener à un problème de contrôle ergodique ou de contrôle ergodique sous contraintes (ergodiques), selon que les contraintes sur les hyperliens sont locales à chaque page ou font intervenir plusieurs pages. On traite à la fois le cas relaxé où les probabilités de passage d'une page à une autre peuvent être des rééls positifs quelconques (on peut par exemple supposer que cette probabilité dépend de la position et des caractères utilisés pour l'hyperlien correspondant) et le cas discret où ces probabilités sont uniformes parmis celles qui sont strictement positives (comme dans la modélisation classique conduisant au calcul du Pagerank). On montre que cette famille de problèmes correspondent à des problèmes de programmation dynamique avec un nombre exponentiel de contrôles, mais où les polytopes des mesures de probabilités de transition admettent des oracles de séparation polynômiaux. On obtient de la sorte des résultats de complexité, ainsi que, sous certaines hypothèses, des algorithmes adaptés à des instances de grande taille, couplant programmation dynamique et relaxation Lagrangienne. Ces algorithmes ont été testés sur un fragment du graphe du web.

Un critère de référencement classique, alternatif au pagerank, est donné par le vecteur propre de Perron. O. Fercoq a abordé le problème associé d'optimisation du référencement, qui se révèle plus difficile que celui du pagerank, en raison de l'absence de propriété de convexité. Cependant, il a développé un algorithme rapide et creux (basé sur des propriétés de rang 1 d'opérateurs intervenant dans le calcul de dérivées du critère) permettant de calculer un optimum local du référencement [62] . Il a enfin donné un algorithme analogue pour optimiser le score “HOTS” de Tomlin.

English version

The goal of the PhD work of O. Fercoq, cosupervised by M. Akian, M. Bouhtou, and S. Gaubert, and supported by a research contract (CRE) of Orange Labs, is to apply optimization and game theory methods to the optimization of online services. We started by investigating the problem of the optimization of referencing, which we modelled by considering a family of compulsory hyperlinks and resources (fixed in advance by the website designer, these constitute the “skeletton” of the website) and also a family of facultative hyperlink or resources (some links may be ommited or some other links may be added).

In [61] , we are approaching the problem of the pagerank optimization in this framework, by applying usual and constrainted Markov decision processes techniques. This problem can indeed be reduced to an ergodic control problem without or with (ergodic) constraints, depending on the fact that hyperlinks constraints are local to each web page or depend on several web pages. We study the relaxed problem where the transition probabilities from one page to another may be any positive real (one may assume for instance that this probability depends on the position and type used for the corresponding hyperlink), as well as the discrete problem where these probabilities are uniform among the positive ones (as in the usual modelisation leading to the Pagerank). We show that these problems can be reduced to dynamic programming problems with exponentially many discrete actions, in which however the polytopes of transition probability measures admit polynomial time separation oracles. We derive from this approach polynomial time complexity results, as well as under some additional assumption, scalable algorithms (adapted to large web graphs), coupling dynamic programming and Lagrange relaxation. The latter have been tested on a real subgraph of the web.

A classical alternative ranking relies on the Perron eigenvector. O. Fercoq treated the associated optimisation problem, which turns out to be harder than in the pagerank case, due to the lack of convexity properties. However, he developed a fast (sparse) algorithm, exploiting the rank 1 properties of operators appearing when computing the derivative of the objective function, allowing one to compute a local optimum [62] . He also developed a similar method to optimize Tomlin's “HOTS” score.

Gestion du revenu appliquée à la tarification de services données/Yield management applied to pricing of data services

Participants : Mustapha Bouhtou [Orange Labs] , Jean-Baptiste Dumont, Stéphane Gaubert.

Le travail de thèse CIFRE de J-B. Dumont, qui a démarré en Septembre 2010, sous la supervision de M. Bouhtou et S. Gaubert, porte sur la tarification de services data et la gestion des ressources dans les réseaux mobiles, qui est abordée à l'aide de techniques de contrôle et d'optimisation stochastique. Dumont a développé un premier modèle de tarification, permettant d'inciter les clients à reporter leur demande en dehors des periodes les plus chargées.

English version

The CIFRE PhD work of J-B. Dumont started in September 2012, under the joint supervision of M. Bouhtou and S. Gaubert. It deals with the pricing of data services and resource allocation in mobile networks. This is addressed through stochastic control and stochastic optimization techniques. Dumont developed a first model of pricing, giving some incentive to the customers to move their demand from loaded to less loaded time periods.